package Array.easy;

import java.util.ArrayList;
import java.util.List;

/**
 * 1. 问题描述
 *      给你一个m行n列的二维网格grid和一个整数k。你需要将grid迁移k次。
 *      每次迁移」操作将会引发下述活动：
 *      位于grid[i][j]的元素将会移动到grid[i][j + 1]。
 *      位于grid[i][n- 1] 的元素将会移动到grid[i + 1][0]。
 *      位于 grid[m- 1][n - 1]的元素将会移动到grid[0][0]。
 *      请你返回k 次迁移操作后最终得到的 二维网格。
 * 2，算法分析
 *      找规律即可，实际上所谓的迁移就是将二维数组中的元素移动的平行移动到下一个位置，如果为边界
 *      就转到下一行，最后一个元素移动到数组的头部
 *
 *      直接写一个辅助函数，oneshift,移动一次
 *      在主函数中调用即可
 *
 *      时间复杂度非常高，因为oneshift函数的时间复杂度为O(n^2)
 *
 *      优化：
 *          实际上上述是一个周期性的，我们可以通过数学公式计算出每个元素在k次前以之后的位置
 *          我们不需要正的移动，而是通过直接通过数学规律找到迁移k次之后该元素的位置，这样时间
 *          复杂度就会非常低
 *          下面建立数学公式：
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 二维网格迁移 {
    public static void main(String[] args) {
        int[][] grid = {{1,2,3},{4,5,6},{7,8,9}};
         shiftGrid(grid, 1);

    }

    public static List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int row = grid.length; int col = grid[0].length;
        while(k >= 1) {
            grid = oneshift(grid);
            k--;
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                System.out.print(grid[i][j]+" ");
            }
            System.out.println();
        }
        List<List<Integer>> ans = new ArrayList<>();
        for(int i = 0; i < row; i++) {
            List<Integer> temp = new ArrayList<>();
            for(int j = 0; j < col; j++) {
                temp.add(grid[i][j]);
            }
            ans.add(temp);
        }
        return ans;
    }

    // 一次迁移之后的网格
    public static int[][] oneshift(int[][] grid) {
        int row = grid.length; int col = grid[0].length;
        int[][] ans = new int[row][col];
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(i == 0 && j == 0) {
                    ans[i][j] = grid[row-1][col-1];
                } else {
                    if(j == 0) { // 求出当前第i行的第一个元素 该元素是原矩阵的前一行的行末
                        ans[i][j] = grid[i-1][col-1];
                    } else {
                        ans[i][j] = grid[i][j-1];
                    }
                }
            }
        }
        return ans;
    }

    public static List<List<Integer>> shiftGrid2(int[][] grid, int k) {


        return null;
    }
}
